package com.problem.leetcode;

/**
 * @author yanzhuoleo
 * @version V1.0
 * @Description: Problem53
 * @date 2018-01-12-上午10:56
 */

public class Problem53 {
    public int maxSubArray(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int index = 0; index < nums.length; ++index) {
            if (max < nums[index] || sum + nums[index] > 0) {

                int maxValue = sum + nums[index] > nums[index] ? sum + nums[index] : nums[index];

                if(maxValue > max) {
                    max = maxValue;
                }

                if (sum + nums[index] > 0) {
                    sum = sum + nums[index];
                }

            } else {
                sum = 0;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new Problem53().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(new Problem53().maxSubArray(new int[]{-1, -2}));
        System.out.println(new Problem53().maxSubArray(new int[]{-2, 1}));
    }

}
